package com.chj.zhongji.class01.test;

public class Code05Test_MaxOneBorderSize {
	public static void setBorderMap(int[][] m, int[][] right, int[][] down) {
		if (m.length == 0) {
			return;
		}
		int row = m.length;
		int col = m[0].length;

		if (m[row - 1][col - 1] == 1) {
			right[row - 1][col - 1] = 1;
			down[row - 1][col - 1] = 1;
		}

		for (int i = col - 2; i >= 0; i--) {
			if (m[row - 1][i] == 1) {
				right[row - 1][i] = right[row - 1][i + 1] + 1;
				down[row - 1][i] = 1;
			}
		}

		for (int i = row - 2; i >= 0; i--) {
			if (m[i][col - 1] == 1) {
				right[i][col - 1] = 1;
				down[i][col - 1] = down[i + 1][col - 1] + 1;
			}
		}

		for (int i = row - 2; i >= 0; i--) {
			for (int j = col - 2; j >= 0; j--) {
				if (m[i][j] == 1) {
					right[i][j] = right[i][j + 1] + 1;
					down[i][j] = down[i + 1][j] + 1;
				}
			}
		}
	}

	public static int getMaxSize(int[][] m) {
		if (m == null || m.length == 0 || m[0].length == 0) {
			return 0;
		}
		int[][] right = new int[m.length][m[0].length];
		int[][] down = new int[m.length][m[0].length];

		setBorderMap(m, right, down);

		System.out.println("----right------");
		printMatrix(right);
		System.out.println("----right------");
		System.out.println("----down------");
		printMatrix(down);
		System.out.println("-----down-----");
		int size = Math.min(m.length, m[0].length);
		for (int i = size; i > 0; i--) {
			if (hasSizeOfBorder(i, right, down)) {
				return i;
			}
		}

		return 0;
	}

	public static boolean hasSizeOfBorder(int size, int[][] right, int[][] down) {
		for (int i = 0; i < down.length - size + 1; i++) {
			for (int j = 0; j < down[0].length - size + 1; j++) {
				if (right[i][j] >= size && down[i][j] >= size && right[i + size - 1][j] >= size
						&& down[i][j + size - 1] >= size) {
					return true;
				}
			}
		}
		return false;
	}

	public static int[][] generateRandom01Matrix(int rowSize, int colSize) {
		int[][] res = new int[rowSize][colSize];
		for (int i = 0; i != rowSize; i++) {
			for (int j = 0; j != colSize; j++) {
				res[i][j] = (int) (Math.random() * 2);
			}
		}
		return res;
	}

	public static void printMatrix(int[][] matrix) {
		for (int i = 0; i != matrix.length; i++) {
			for (int j = 0; j != matrix[0].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		int[][] matrix = generateRandom01Matrix(7, 8);
		printMatrix(matrix);
		System.out.println(getMaxSize(matrix));
	}

}
